Online-Academy
Look, Read, Understand, Apply

Data Structure

Sorting Q and A

Write Time complexity for sorting algorithms

Answer:

Good for small dataset
SortingTime Complexity (Worst case)Verdicts
Bubble SortO(n2)Not Good
Insertion SortO(n2)
Selection SortO(n2)For small dataset
Merge SortO(nlong(n))Stable sort
Quick SortO(nlong(n))Works good for general purpose
Heap SortO(nlong(n))Good

What are comparison sort and non-comparison sort?

Answer: Comparison sort algorithms determine the order of elements by comparing them using relational operators. Insertion sort, bubble sort, selection sort, merge sort, quick sort, heap sort are comparison sorts. Non-comparision sort algorithms donot compare elements directly, it uses properties of data to sort elements. Radix sort is non-comparison sort.

How quick sort works?

Answer: QuickSort is a divide-and-conquer sorting algorithm that works by recursively partitioning an array around a pivot element.

  1. First Choose a Pivot, you can take the first element (but not necessary)
  2. The goal is to partition the array such that:
  3. Elements less than the pivot go to its left.
  4. Elements greater than the pivot go to its right.
Above steps will create sub array around the pivot. With those sub arrays repeat above steps (1 - 4) until the array is sorted.

How merge sort works?

Answer: Merge Sort is a divide-and-conquer sorting algorithm that recursively splits an array into smaller subarrays (upto array of one element), sorts them, and then merges them back together.

How Insertion sort works?

Answer: Insertion Sort is a simple, in-place comparison-based sorting algorithm that builds the final sorted array one element at a time. It is efficient for small datasets and nearly sorted data, with a best-case time complexity of O(n).

  • Take the second element as current element (assume the first element is already sorted).
  • Compare the current element with the previous elements.
  • Shift all larger elements one position to the right.
  • Insert the current element into its correct position.
  • Repeat until the entire array is sorted.

How Selection Sort Works?

Answer: Selection Sort works by repeatedly finding the minimum (or maximum) element from the unsorted part of the array and putting it at the beginning (or at the end).

  1. n is size of array, i = 0
  2. Find the minimum element (or maximum) in the array of size n-i.
  3. Swap it with the first (or last) element .
  4. i = i + 1
  5. Repeat until the steps from 2 to 4 until entire array is sorted.

How heap sort works?

Answer: Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It has O(n log n) time complexity in all cases and O(1) auxiliary space (in-place), making it efficient for large datasets.

  • First Create Max heap or min heap tree from given data.
  • Repeatedly extract the max (or min) element from the heap tree and store in array and rebuild the heap.

    • What is a heap tree?

    Answer: A heap tree (or simply heap) is a specialized complete binary tree that satisfies the heap property. It is commonly used to implement priority queues and forms the basis for the Heap Sort algorithm.

    Key Properties of a Heap

  • It is a Complete Binary Tree Structure
  • All levels are fully filled except possibly the last level, which is filled from left to right. This allows heaps to be efficiently stored in arrays (no pointers needed).

    • Heap Property

  • Max-Heap: Every parent node >= its children (root = maximum element).
  • Min-Heap: Every parent node <= its children (root = minimum element).

    • How a heap can be represented as an array?

    Answer: A heap is represented as an array where:

    For an element at index i:

  • Left child = 2*i + 1
  • Right child = 2*i + 2
  • Parent = (i-1)/2